Network Function Virtualization (NFV) aims to simplify deployment of networkservices by running Virtual Network Functions (VNFs) on commercialoff-the-shelf servers. Service deployment involves placement of VNFs andin-sequence routing of traffic flows through VNFs comprising a Service Chain(SC). The joint VNF placement and traffic routing is called SC mapping. In aWide-Area Network (WAN), a situation may arise where several traffic flows,generated by many distributed node pairs, require the same SC; then, a singleinstance (or occurrence) of that SC might not be enough. SC mapping withmultiple SC instances for the same SC turns out to be a very complex problem,since the sequential traversal of VNFs has to be maintained while accountingfor traffic flows in various directions. Our study is the first to deal withthe problem of SC mapping with multiple SC instances to minimize networkresource consumption. We first propose an Integer Linear Program (ILP) to solvethis problem. Since ILP does not scale to large networks, we develop acolumn-generation-based ILP (CG-ILP) model. However, we find that exactmathematical modeling of the problem results in quadratic constraints in ourCG-ILP. The quadratic constraints are made linear but even the scalability ofCG-ILP is limited. Hence, we also propose a two-phase column-generation-basedapproach to get results over large network topologies within reasonablecomputational times. Using such an approach, we observe that an appropriatechoice of only a small set of SC instances can lead to a solution very close tothe minimum bandwidth consumption. Further, this approach also helps us toanalyze the effects of number of VNF replicas and number of NFV nodes onbandwidth consumption when deploying these minimum number of SC instances.
展开▼
